package cn.xkai.exercise.a;

import com.google.gson.Gson;

/**
 * @description: 对角线遍历
 * 自己的思路：未完成
 * 借鉴的思路：判断是否为越界情况：不越界正常行加一，越界行加二，列减一;此处不理解的拿张草稿纸将循环中row和col的值遍历写一下对照矩阵图就明白了.
 * 心得：思路大致一样，在反向输出和越界判断上未完成(对角线遍历最好把矩阵图完整的画一遍)
 * @author: kaixiang
 * @date: 2022-06-22
 **/
public class Solution7 {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        //存放数组
        int[] ans = new int[m * n];
        //对角线方向次数
        int count = n + m - 1;
        //定义初始化 行标记，列标记，存放数组索引
        int row = 0, col = 0, index = 0;
        //开始对角线循环
        for (int i = 0; i < count; i++) {
            //判断对角线方向（因题目初始从右上（即i=0）开始）：偶数右上，奇数左下
            if (i % 2 == 0) {
                //右上操作
                while (row >= 0 && col < n) {
                    //将矩阵数存入存放数组
                    ans[index] = mat[row][col];
                    //索引后移
                    index++;
                    //右上规律：行减一，列加一
                    row--;
                    col++;
                }
                //判断是否为越界情况：不越界正常行加一，越界行加二，列减一；
                //（此处不理解的拿张草稿纸将循环中row和col的值遍历写一下对照矩阵图就明白了）
                if (col < n) {
                    row++;
                }
                else {
                    row += 2;
                    col--;
                }
            }
            //左下操作：按规律与右上相反即可
            else {
                while (row < m && col >= 0) {
                    ans[index] = mat[row][col];
                    index++;
                    row++;
                    col--;
                }
                if (row < m) {
                    col++;

                } else {
                    row--;
                    col += 2;
                }
            }
        }
        // 返回存放数组
        return ans;
    }

    public static void main(String[] args) {
        int[] a1 = {2, 5};
        int[] a2 = {8, 4};
        int[] a3 = {0, -1};
        int[][] a = {a1, a2, a3};
        Solution7 solution7 = new Solution7();
        System.out.println(new Gson().toJson(solution7.findDiagonalOrder(a)));
    }
}
